import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * 224. 基本计算器
 * https://leetcode-cn.com/problems/basic-calculator/
 */
public class Solutions_224 {
    public static void main(String[] args) {
        String str1 = "1 + 1";  // output: 2
        String str2 = " 2-1 + 2 ";  // output: 3
        String str3 = "2147483647";  // output: 2147483647
        String str4 = "(1+(4+5+2)-3)+(6+8)";  // output: 23

        List<String> inputs = new ArrayList<>();
        inputs.add(str1);
        inputs.add(str2);
        inputs.add(str3);
        inputs.add(str4);

        for (String input : inputs) {
            int result = calculate(input);
            System.out.println(result);
        }
    }

    /**
     * 解题思路：栈实现
     * 栈中存储系数和数字
     * 运算符是 +，系数为 1，运算符是 -，系数为 -1
     * 遍历字符串，对不同的字符进行相应的处理
     * 1. 空格：跳过
     * 2. 数字：处理并计算连续的数字，最终累加到 res 中
     * 3. 开括号：当前 res 入栈，系数入栈
     * 4. 闭括号：系数出栈，数字出栈，括号前的系数出栈
     *      系数 * 数字 + 括号前的系数出栈，赋值给 res
     * 5. 加号：改变系数为 1
     * 6. 减号：改变系数为 -1
     */
    public static int calculate(String s) {
        char[] arr = s.toCharArray();
        LinkedList<Integer> stack = new LinkedList<>();
        int opt = 1;
        int res = 0;

        for (int i = 0; i < arr.length; i++) {
            if (arr[i] == '+') {
                opt = 1;
            } else if (arr[i] == '-') {
                opt = -1;
            } else if (arr[i] == ' ') {
                continue;
            } else if (arr[i] == '(') {
                // 括号前的计算结果，存储到栈中，并将原有的计算结果清零
                stack.push(res);
                res = 0;
                // 括号前的运算符号，存储到栈中，并还原符号为 +
                stack.push(opt);
                opt = 1;
            } else if (arr[i] == ')') {
                // 一个括号中的运算结束，最终 res = 当前括号中的运算结果 res * 系数 + 括号前的计算结果
                res = stack.pop() * res + stack.pop();
                opt = 1;
            } else {
                int cur = arr[i] - '0';
                // 数字
                while (i < arr.length - 1 && Character.isDigit(arr[i + 1])) {
                    cur = cur * 10 + arr[i + 1] - '0';
                    i ++;
                }
                // 累加到 res 中
                res += cur * opt;
            }
        }
        return res;
    }
}
